package com.leetcode.algorithm.y22.m08.w2;

/**
 * 1422. 分割字符串的最大得分
 * 
 * https://leetcode.cn/problems/maximum-score-after-splitting-a-string/
 * 
 * @author jie.deng
 *
 */
class Question1422Solution01 {

	public int maxScore(String s) {
		int len = s.length();
		int[] prefixArr = new int[len];
		prefixArr[0] = s.charAt(0) == '1' ? 1 : 0;
		for (int i = 1; i < len; i++) {
			prefixArr[i] = prefixArr[i - 1] + (s.charAt(i) == '1' ? 1 : 0);
		}
		int maxScore = 0;
		for (int i = 1; i < len; i++) {
			int score = (i - prefixArr[i - 1]) + (prefixArr[len - 1] - prefixArr[i - 1]);
			if (maxScore < score) {
				maxScore = score;
			}
		}
		return maxScore;
	}

}